package algorithm.leetcode.I1to100;

import java.util.Arrays;

public class Q16 {

    public int threeSumClosest(int[] nums, int target) {
        int res = Integer.MAX_VALUE >> 1;
        Arrays.sort(nums);

        for (int i = 0; i < nums.length-2; i++) {
            int j = i+1, k = nums.length-1;

            while (j < k) {
                int gap = nums[i] + nums[j] + nums[k] - target;
                int absGap = Math.abs(gap);
                if (absGap <= Math.abs(res - target)) {
                    res = nums[i] + nums[j] + nums[k];
                }
                if (gap > 0) k--;
                else if (gap < 0) j++;
                else {k--; j++;}
            }
        }

        return res;

    }

    public static void main(String[] args) {
        Q16 q16 = new Q16();
        System.out.println(q16.threeSumClosest(new int[]{1,1,-1,-1,3}, -1));
    }

}
